
//Copyright 1997-2009 Syrinx Development, Inc.
//This file is part of the Syrinx Web Application Framework (SWAF).
// == BEGIN LICENSE ==
//
// Licensed under the terms of any of the following licenses at your
// choice:
//
//  - GNU General Public License Version 3 or later (the "GPL")
//    http://www.gnu.org/licenses/gpl.html
//
//  - GNU Lesser General Public License Version 3 or later (the "LGPL")
//    http://www.gnu.org/licenses/lgpl.html
//
//  - Mozilla Public License Version 1.1 or later (the "MPL")
//    http://www.mozilla.org/MPL/MPL-1.1.html
//
// == END LICENSE ==
using System;
using System.Diagnostics;

namespace Swaf.Container
{
	/// <summary>
	/// Summary description for LinkedList.
	/// </summary>
	public class LinkedList
	{
		DoubleLinkNode m_head;
		DoubleLinkNode m_tail;

		public LinkedList()
		{
		}

		public virtual NodeRef Head {get{return m_head;}}
		public virtual NodeRef Tail {get{return m_tail;}}

		public virtual NodeRef this [int i]
		{
			get
			{
				NodeRef r = Head;
				for(int p = 0; p < i && r != null; ++p, r = r.Next);
				return r;
			}
		}

		public virtual NodeRef addTail(object element)
		{
			DoubleLinkNode n = new DoubleLinkNode(element);
			if(m_tail != null)
			{
				m_tail.Next = n;
				n.Prev = m_tail;
				m_tail = n;
			}
			else
			{
				m_head = n;
				m_tail = n;
			}
			return n;
		}

		public virtual NodeRef addHead(object element)
		{
			DoubleLinkNode n = new DoubleLinkNode(element);
			if(m_head != null)
			{
				m_head.Prev = n;
				n.Next = m_head;
				m_head = n;
			}
			else
			{
				m_head = n;
				m_tail = n;
			}
			return n;
		}

		public virtual void moveNode(NodeRef nodeRef, NodeRef locationRef, bool afterLocation)
		{
			Debug.Assert(nodeRef != null);
			Debug.Assert(locationRef != null);

			remove(nodeRef);
			insertNode((DoubleLinkNode)nodeRef, (DoubleLinkNode)locationRef, afterLocation);
		}

		public virtual NodeRef insert(object element, NodeRef locationRef, bool afterLocation)
		{
			DoubleLinkNode node = new DoubleLinkNode(element);
			insertNode(node, (DoubleLinkNode)locationRef, afterLocation);
			return node;
		}

		protected virtual void insertNode(DoubleLinkNode node, DoubleLinkNode location, bool afterLocation)
		{
			if(afterLocation)
			{
				if(m_tail == location)
					m_tail = node;
				node.m_prev = location;
				node.m_next = location.m_next;
				if(node.Next != null)
					node.m_next.m_prev = node;
			}
			else
			{
				if(m_head == location)
					m_head = node;
				node.m_next = location;
				node.m_prev = location.m_prev;
				location.m_prev = node;
				if(node.Prev != null)
					node.m_prev.m_next = node;
			}
		}


		/// <summary>
		/// 
		/// </summary>
		/// <remarks>This method assumes that nref passed is actually from this list.
		/// If it is from a different LinkedList, bad things will happen.</remarks>
		/// <param name="nref"></param>
		public virtual void remove(NodeRef nref)
		{
			if(nref == null) return;

			if(nref == m_head)
				m_head = (DoubleLinkNode)m_head.Next;
			if(nref == m_tail)
				m_tail = (DoubleLinkNode)m_tail.Prev;

			DoubleLinkNode n = (DoubleLinkNode)nref;
			if(n.Next != null)
				((DoubleLinkNode)n.Next).Prev = n.Prev;
			if(n.Prev != null)
				((DoubleLinkNode)n.Prev).Next = n.Next;
		}

        public interface NodeRef
		{
			NodeRef Next {get;}
			NodeRef Prev {get;}
			object Element {get;}
		}

		protected class DoubleLinkNode : NodeRef
		{
			protected internal DoubleLinkNode m_next;
			protected internal DoubleLinkNode m_prev;
			protected internal object m_element;

			public DoubleLinkNode(object element)
			{
				m_element = element;
			}

			public NodeRef Next
			{
				get {return m_next;}
				set {m_next = (DoubleLinkNode)value;}
			}

			public NodeRef Prev
			{
				get {return m_prev;}
				set {m_prev = (DoubleLinkNode)value;}
			}

			public object Element
			{
				get {return m_element;}
				set {m_element = value;}
			}
		}

	}
}
